#include "headfiles.h"
#include <vector>

using namespace std;

void printPath(vector<NODE *>&node_vec, int sum) {
	size_t size = node_vec.size();
	size_t i, j;
	int tmp_sum = 0;
	for (i = 0; i < size; i++) {
		tmp_sum += node_vec[size - 1 - i]->i;
		if (tmp_sum == sum) {
			cout << "Path: " << endl;
			for (j = size - 1 - i; j < size; j++) {
				cout << node_vec[j]->i << "\t";
			}
			cout << endl;
		}
	}

	return;
}

bool calcPaths(vector<NODE *> &node_vec, NODE *head, int sum) {
	// Reached a leaf, return directly
	if (head == NULL) {
		return true;
	}

	// Not a left, add the node to the vector
	node_vec.push_back(head);

	// Check whether there is a set of nodes with the 
	// sum to the sum.
	printPath(node_vec, sum);
	
	// Calculate paths with its left child
	calcPaths(node_vec, head->left, sum);

	// Calcuate path with its right child
	calcPaths(node_vec, head->right, sum);

	// Finally, we need to erase the head node in the vector
	// It is the last elem in the vector
	vector<NODE *>::iterator it = node_vec.end();
	--it;
	node_vec.erase(it);

	return true;
}

bool calcPathsWRTSum(NODE *head, int sum) {
	vector<NODE *> node_vec;

	return calcPaths(node_vec, head, sum);
}

